package com.hy;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:2492两个城市间路径的最小分数
 * <p>
 * 给你一个正整数 n ，表示总共有 n 个城市，城市从 1 到 n 编号。给你一个二维数组 roads ，其中 roads[i] = [ai, bi, distancei] 表示城市 ai 和 bi 之间有一条 双向 道路，
 * 道路距离为 distancei 。城市构成的图不一定是连通的。
 * 两个城市之间一条路径的 分数 定义为这条路径中道路的 最小 距离。
 * 城市 1 和城市 n 之间的所有路径的 最小 分数。
 * 注意：
 * 一条路径指的是两个城市之间的道路序列。
 * 一条路径可以 多次 包含同一条道路，你也可以沿着路径多次到达城市 1 和城市 n 。
 * 测试数据保证城市 1 和城市n 之间 至少 有一条路径。
 *
 * User:Mr.Du
 * Date:2024/4/23
 * Time:15:08
 */
public class MinScore {

    /**
     * 计算最小通行分数
     * @param n 城市数量，城市的编号从1到n
     * @param roads 道路数组，每个道路由三个整数[x, y, z]组成，表示城市x和城市y之间有一条道路，通行分数为z
     * @return 返回从城市1到其他任何城市的最小通行分数；如果无法到达其他城市，则返回Integer.MAX_VALUE
     */
    public int minScore(int n, int[][] roads) {
        // 初始化城市连接列表和访问标记数组
        List<int[]>[] list = new ArrayList[n+1];
        boolean[] visited = new boolean[n+1];
        Arrays.setAll(list, e -> new ArrayList<>());

        // 建立城市之间的连接关系
        for(int[] road : roads){
            int x = road[0], y = road[1], z = road[2];
            list[x].add(new int[]{y, z});
            list[y].add(new int[]{x, z});
        }

        // 使用BFS队列进行遍历
        Queue<Integer> queue = new ArrayDeque<>();
        int res = Integer.MAX_VALUE; // 用于记录最小通行分数
        queue.offer(1); // 从城市1开始遍历
        while(!queue.isEmpty()){
            int x = queue.poll();
            visited[x] = true; // 标记当前城市已访问
            for(int[] curs : list[x]){
                int ne = curs[0], cd = curs[1]; // 遍历与当前城市连接的城市
                if(!visited[ne]){
                    visited[ne] = true;
                    queue.offer(ne); // 将未访问过的城市加入队列
                }
                res = Math.min(res, cd); // 更新最小通行分数
            }
        }
        return res;
    }

    // 会超出内存限制
    public int minScore1(int n, int[][] roads) {
        List<int[]>[] list = new List[n+1];
        boolean[][] visited = new boolean[n+1][n+1];
        Arrays.setAll(list, e -> new ArrayList<>());
        for(int[] road : roads){
            int x = road[0], y = road[1], z = road[2];
            list[x].add(new int[]{y, z});
            list[y].add(new int[]{x, z});
        }
        Queue<Integer> queue = new ArrayDeque<>();
        int res = Integer.MAX_VALUE;
        queue.offer(1);
        while(!queue.isEmpty()){
            int x = queue.poll();
            for(int[] curs : list[x]){
                int ne = curs[0], cd = curs[1];
                if(visited[ne][x] || visited[x][ne]) continue;
                visited[ne][x] = true;
                visited[x][ne] = true;
                res = Math.min(res, cd);
                queue.offer(ne);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] roads = new int[][]{{1,2,2},{1,3,4},{3,4,7}};
        System.out.println(new MinScore().minScore(4, roads));
    }
}
